package test;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author 豆包LU
 * @date 2023/4/11 10:31
 */
public class LFUCachePriorityQueue<K, V> {

    public static void main(String[] args) {
        // 创建容量为 3 的 LFU 缓存
        LFUCachePriorityQueue cache = new LFUCachePriorityQueue(3);

        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        CacheNode c1 = (CacheNode) cache.get(1);//2
        CacheNode c2 = (CacheNode) cache.get(2);//2
        CacheNode c3= (CacheNode) cache.get(3);//2
        System.out.println("键："+c1.key+",频率："+c1.frequency+",时间戳："+c1.timestamp+","+"键："+c2.key+",频率："+c2.frequency+",时间戳："+c2.timestamp+"键："+c3.key+",频率："+c3.frequency+",时间戳："+c3.timestamp);
        cache.put(4, "four");//1,c1移除
        CacheNode c4 = (CacheNode) cache.get(4);//2
        System.out.println("键："+c4.key+",频率："+c4.frequency+",时间戳："+c4.timestamp+","+"键："+c2.key+",频率："+c2.frequency+",时间戳："+c2.timestamp+"键："+c3.key+",频率："+c3.frequency+",时间戳："+c3.timestamp);
        cache.get(2);//3
        cache.get(4);//3
        System.out.println("键："+c4.key+",频率："+c4.frequency+",时间戳："+c4.timestamp+","+"键："+c2.key+",频率："+c2.frequency+",时间戳："+c2.timestamp+"键："+c3.key+",频率："+c3.frequency+",时间戳："+c3.timestamp);
        cache.put(5, "five");//1,c3移除
        CacheNode c5= (CacheNode) cache.get(5);//5
        System.out.println("键："+c5.key+",频率："+c5.frequency+",时间戳："+c5.timestamp+","+"键："+c4.key+",频率："+c4.frequency+",时间戳："+c4.timestamp+"键："+c2.key+",频率："+c2.frequency+",时间戳："+c2.timestamp);

    }
    private final int capacity; // 缓存容量
    private final Map<K, CacheNode<K, V>> cache; // 存储缓存数据的 HashMap
    private final PriorityQueue<CacheNode<K, V>> pq; // 存储缓存数据的优先队列，按使用频率排序

    public LFUCachePriorityQueue(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        // 创建一个优先队列，使用自定义的比较器按使用频率和时间戳排序
        this.pq = new PriorityQueue<>((a, b) -> {
            int freqCompare = Integer.compare(a.frequency, b.frequency); // 按使用频率升序排序
            if (freqCompare != 0) {
                return freqCompare;
            } else {
                return Long.compare(a.timestamp, b.timestamp); // 按时间戳升序排序
            }
        });
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        CacheNode<K, V> node = cache.get(key);
        // 更新节点的使用频率和时间戳
        node.frequency++;
        node.timestamp = System.nanoTime();
        // 更新优先队列中的节点位置
        pq.remove(node);
        pq.offer(node);

        return (V) node;
    }

    public void put(K key, V value) {
        if (capacity <= 0) {
            return;
        }

        // 如果缓存中已存在该键，则更新其值并更新使用频率和时间戳
        if (cache.containsKey(key)) {
            CacheNode<K, V> node = cache.get(key);
            node.value = value;
            node.frequency++;
            node.timestamp = System.nanoTime();
            // 更新优先队列中的节点位置
            pq.remove(node);
            pq.offer(node);
        } else {
            // 如果缓存容量已满，则移除使用频率最低的节点
            if (cache.size() >= capacity) {
                CacheNode<K, V> removedNode = pq.poll();
                cache.remove(removedNode.key);
            }

            // 创建新节点，并添加到缓存和优先队列中
            CacheNode<K, V> newNode = new CacheNode<>(key, value);
            cache.put(key, newNode);
            pq.offer(newNode);
        }
    }

    private static class CacheNode<K, V> {
        private final K key; // 键
        private V value; // 值
        private int frequency; // 使用频率
        private long timestamp; // 时间戳

        public CacheNode(K key, V value) {
            this.key = key;
            this.value = value;
            this.frequency = 1; // 初始使用频率为1
            this.timestamp = System.nanoTime(); // 初始时间戳为当前时间戳
        }
    }
}
